Identification of $\cal K$ Most Vulnerable Nodes in Multi-layered Network Using a New Model of Interdependency

摘要

The critical infrastructures of the nation including the power grid and thecommunication network are highly interdependent. Recognizing the need for adeeper understanding of the interdependency in a multi-layered network,significant efforts have been made by the research community in the last fewyears to achieve this goal. Accordingly a number of models have been proposedand analyzed. Unfortunately, most of the models are over simplified and, assuch, they fail to capture the complex interdependency that exists betweenentities of the power grid and the communication networks involving acombination of conjunctive and disjunctive relations. To overcome thelimitations of existing models, we propose a new model that is able to capturesuch complex interdependency relations. Utilizing this model, we providetechniques to identify the $\cal K$ most vulnerable nodes of an interdependentnetwork. We show that the problem can be solved in polynomial time in somespecial cases, whereas for some others, the problem is NP-complete. Weestablish that this problem is equivalent to computation of a {\em fixed point}of a multilayered network system and we provide a technique for its computationutilizing Integer Linear Programming. Finally, we evaluate the efficacy of ourtechnique using real data collected from the power grid and the communicationnetwork that span the Maricopa County of Arizona.